import java.util.Deque;
import java.util.LinkedList;

public class MySort {
    /**
     * 冒泡排序
     * 时间复杂度:O(n^2)
     * 空间复杂度:o(1)
     * 稳定性：稳定
     */
    public static void bubble(int[]array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]) {
                    swap(array,i,j);
                    flg=true;
                }
            }
            if(!flg) {
               return;
            }
        }
    }
    /**
     * 堆排序
     * 时间复杂度:O(nlogn)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void HeapSort(int[]array) {
    //升序
        System.out.println('1');
        createBigHeap(array);
        //变成大根堆
        //取堆头不断入队尾同时size--
        int size= array.length-1;
        while (size!=0) {
            swap(array,0,size);
            shiftDown(array,0,size);
            size--;
        }
    }
    public static void createBigHeap(int[]array) {
        for (int i = (array.length-1-1)/2; i >=0 ; i--) {
            shiftDown(array,i,array.length);
        }
    }
    //大根堆
    private static void shiftDown(int[]array,int parent,int len) {
        int child=parent*2+1;
        while (child<len) {
            if(child+1<array.length&&array[child+1]>array[child]) {
                child++;
            }
            if(array[child]>array[parent]) {
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else {
                break;
            }
        }
    }
    /**
     * 两端选择排序
     */
    public static void twoSelectSort(int[]array) {
        int min=0;
        int max=0;
        int left=0;
        int right=array.length-1;
        while (left<right) {
            max=left;
            min=left;
            for (int i = left+1; i <=right ; i++) {
                if(array[min]>array[i]) {
                    min=i;
                }
                if(array[max]<array[i]) {
                    max=i;
                }
            }
            //这里有可能把最大值换到array[min]
            if(max==left) {
                max=min;
            }
            swap(array,min,left);
            swap(array,max,right);
            left++;
            right--;
        }
    }
    /**
     * 选择排序
     * 时间复杂度:O(N^2)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void selectSort(int []array) {
        int minIndex=0;
        for (int i = 0; i < array.length; i++) {
            minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if(array[minIndex]>array[j]) {
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[]array,int left,int right) {
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }

    /**
     * 插入排序
     * 时间复杂度:O(N^2)
     * 空间复杂度:O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void insertSort(int array[]) {
        //插入排序
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=0; j--) {
                if(array[j]>tmp) {
                       array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    /**
     * 插入排序控制边界
     * @param array
     */
    public static void insertSort1(int array[],int left,int right) {
        //插入排序
        for (int i = left+1; i <= right; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=left; j--) {
                if(array[j]>tmp) {
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    /**
     * 希尔排序
     * 时间复杂度:O(N^1.3)
     * 空间复杂度:O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void ShellSort(int[]array) {
        int size=array.length;
        while (size>1) {
            size/=2;
           func(array,size);
        }
        insertSort(array);
    }
    public static void func(int[]array,int gap) {
        for (int i = gap; i <array.length ; i++) {
            int tmp=array[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if(array[j]>tmp) {
                    array[j+gap]=array[j];
                }else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    /**
     * 快速排序递归实现
     */
    public static void quickSort1(int[] array) {

        quick(array,0,array.length-1);

    }

    /**
     * 用这个实现递归
     * 时间复杂度：最好情况：nlogn 最坏情况n^2
     * 空间复杂度：最好情况：logn 最坏情况n
     *稳定性：不稳定
     *  @param array
     */
    private static void quick(int[]array,int left,int right) {
        if(left>=right) {
            return;
        }
        if(right-left+1<=80) {
            //插入排序
            insertSort1(array,left,right);
            return;
        }
        int p=MiddleThree(array,left,right);
        swap(array,p,left);
       int index= partition1(array,left,right);
        quick(array,left,index-1);
        quick(array,index+1,right);

    }


        /**
         * 找基准
         * @param array
         * @param left
         * @param right
         * @return
         */
    private static int partition1(int[] array,int left,int right) {

        int tmp=array[left];
        while (left<right) {
            while (left<right&&array[right]>=tmp) {
                right--;
            }
            array[left]=array[right];
            while (left<right&&array[left]<=tmp) {
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }

    /**
     * 找基准
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array,int left,int right) {
        int tmp=array[left];
        int p=left;
        while (left<right) {
            //先走右边
            while (left<right&&array[right]>=tmp) {
                right--;
            }
            while (left<right&&array[left]<=tmp) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,p,left);
        return left;
    }
    /**
     * 三数取中法
     */
    public static int MiddleThree(int[]array,int left,int right) {
        int mid=(left+right)>>>1;
        if(array[left]<array[right]) {
            if(array[mid]>array[right]) {
                return right;
            }
           else if(array[mid]<array[left]) {
                return left;
            }else {
                return mid;
            }
        }
        if(array[left]>array[right]) {
            if(array[mid]<array[right]) {
                return right;
            }
            else if(array[mid]>array[left]) {
                return left;
            }else {
                return mid;
            }
        }
        return mid;
    }
    /**
     * 非递归实现
     * @param array
     */
   public static void quickSort(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length-1;
            int pivot = partition(array,left,right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
            while (!stack.isEmpty()) {
                right = stack.pop();
                left = stack.pop();
                pivot = partition(array,left,right);
                if(pivot > left+1) {
                    stack.push(left);
                    stack.push(pivot-1);
                }
                if(pivot < right-1) {
                    stack.push(pivot+1);
                    stack.push(right);
                }
            }
    }

    /**
     * 归并排序非递归
     * @param array
     */
    public static void mergeSort(int[]array) {
       int gap=1;
       while (gap<array.length) {
           for (int i = 0; i < array.length; i+=gap*2) {
               int mid= i +gap-1;
               if(mid>=array.length) {
                   mid=array.length-1;
               }
               int right=mid+gap;
                if(right>=array.length) {
                    right=array.length-1;
                }
                merge(array,i,right,mid);
           }
           gap*=2;
       }
    }

        /**
         * 归并排序
         * 时间复杂度:O(nlongn)
         * 空间复杂度：O(n)
         * 稳定性：稳定
         */
    public static void mergeSort1(int[]array) {
        mergeSortFunc(array,0,array.length-1);
    }
    private static void mergeSortFunc(int[]array,int left,int right) {
        if(left>=right) {
            return;
        }
        int mid=left-(left-right)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        //合并
        merge(array,left,right,mid);

    }
    private static void merge(int[]array,int left,int right,int mid) {
        int e1=left;
        int e2=mid+1;
        int k=0;
        int[]ret=new int[right-left+1];
        while (e1<=mid&&e2<=right) {
            if(array[e1]<array[e2]) {
                ret[k++]=array[e1++];
            }else {
                ret[k++]=array[e2++];
            }
        }
        while (e1<=mid) {
            ret[k++]=array[e1++];
        }
        while (e2<=right) {
            ret[k++]=array[e2++];
        }
        System.arraycopy(ret, 0, array, left, ret.length);
        System.out.println("1");
    }

}
